package 单周赛.history;

import java.util.HashMap;
import java.util.Map;

/**
 *
 */
public class 第328场单周赛 {

    public static void main(String[] args) {

        System.out.println(differenceOfSum(new int[]{1, 15, 6, 3}));

        rangeAddQueries(2, new int[][]{{0, 0, 1, 1}});

        //[2,3,1,3,2,3,3,3,1,1,3,2,2,2]
        //18
        System.out.println(countGood(new int[]{3, 1, 4, 3, 2, 2, 4}, 2));

    }

    public static int differenceOfSum(int[] nums) {
        int sum1 = 0, sum2 = 0;
        for (int num : nums) {
            sum1 += num;

            int n = num;
            while (n > 0) {
                sum2 += n % 10;
                n /= 10;
            }
        }
        return Math.abs(sum1 - sum2);
    }

    public static int[][] rangeAddQueries(int n, int[][] queries) {
        int[][] ans = new int[n][n];

        for (int[] query : queries) {
            for (int row = query[0]; row <= query[2]; row++) {
                for (int column = query[1]; column <= query[3]; column++) {
                    ans[row][column]++;
                }
            }
        }

        return ans;
    }

    //6293. 统计好子数组的数目
    //给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
    //一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
    //子数组 是原数组中一段连续 非空 的元素序列。

    /**
     * 滑动窗口
     * 要求连续的子数组，可以分解为求已 nums[right] 结尾 nums[left] 开头的
     * 好子数组数目，其中 left<right ，如果某个区间 [left,right] 满足 >=k
     * 的条件，那么 [left-1,right] 也一定满足，因为其区间更大，那么我们尽可能
     * 将 left 变大，使得[left,right]满足条件，那么以 right 结尾的好数目为
     * left+1
     * 可以使用哈希表存储每个数字出现的次数，当前新增数字可以增加的对数为哈希表
     * 中已经出现的次数
     */
    public static long countGood(int[] nums, int k) {
        long sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int curK = 0;
        int left = 0, right = 0;
        while (right < nums.length) {
            curK += map.getOrDefault(nums[right], 0);
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            right++;

            while (left < right && curK >= k) {
                // 使得区间[left,right]里面的好数始终是 >=k 的left最大索引
                if (curK - map.get(nums[left]) + 1 < k) {
                    break;
                }
                curK -= map.get(nums[left]) - 1;
                map.put(nums[left], map.get(nums[left]) - 1);
                left++;
            }

            if (curK >= k) sum += left + 1;
        }
        return sum;
    }

}
